#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>

#define FILE_MAX_SIZE 1024*1024
#define MAX_CHAR_LEN 1024

typedef struct st{
	struct st* sts[26];
}Atrie;


void print_to_tail(char* prefix,Atrie* pt,int len){
	assert(pt!=NULL && prefix!=NULL);
	int i;
	int cc=0;
	for(i=0;i<26;i++){
		//printf("%x,%d\n",pt->sts[i],len);
		if(pt->sts[i]!=NULL){
			prefix[len]=i+'a';
			prefix[len+1]='\0';
			print_to_tail(prefix,pt->sts[i],len+1);
			prefix[len]='\0';
			cc++;
		}
	}
	if(cc==0){
		printf("%s\n",prefix);
	}
}

void find_prefix(Atrie* pt,char* word){
	assert(pt!=NULL && word!=NULL);
	printf("find prefix:%s\n",word);
	int i=0;
	char ch=word[i];
	while(ch!='\0'){
		int pos=ch-'a';		
		if(pt->sts[pos]!=NULL){
			pt=pt->sts[pos];
		}else{
			printf("not found at %c\n",ch);
			return;
		}
		i++;
		ch=word[i];
	}
	char* w=(char*)malloc(MAX_CHAR_LEN);
	int len=strlen(word);
	strcpy(w,word);
	w[len]='\0';
	print_to_tail(w,pt,len);
}

int main(){
	/*
	char* buffer=(char*)malloc(FILE_MAX_SIZE);
	
	FILE* fp=fopen("/Users/Liq/op/google/learnc/tools/words.dat","r");
	assert(fp!=NULL);
	char c;
	int i=0;
	while( (c=fgetc(fp))!=EOF && i<FILE_MAX_SIZE){
		buffer[i]=c;
		i++;
	}
	buffer[i]='\0';
	fclose(fp);
	*/
	char* words[]={"bet","bat","banana","benifit","ben"};
	int i,j;
	
	Atrie root;
	memset(&root,0,sizeof(Atrie));
	Atrie* pt=&root;
	for(i=0;i<5;i++){
		char ch=tolower(words[i][0]);
		j=0;
		pt=&root;
		while(ch!='\0'){
			int pos=ch-'a';
			assert(pt!=NULL);
			if(pt->sts[pos]==NULL){				
				Atrie* tmp=(Atrie*)malloc(sizeof(Atrie));
				memset((void*)tmp,0,sizeof(Atrie));
				pt->sts[pos]=tmp;
			}
			assert(pt->sts[pos]!=NULL);
			pt=pt->sts[pos];
			j++;
			if(words[i][j]=='\0')
				break;
			ch=tolower(words[i][j]);
		}
	}
	
//	printf("%x\n",root.sts[1]);
//	for(i=0;i<26;i++)		printf("%x\n",root.sts[1]->sts[i]);
		
	find_prefix(&root,"ba");
	find_prefix(&root,"b");
	find_prefix(&root,"be");	
}